package com.ljy.my_study.lintcode.搜索二维矩阵II;
/** 
* @author James
* @date 2018年9月28日 
*/
public class TestMain {
//	描述
//	写出一个高效的算法来搜索m×n矩阵中的值，返回这个值出现的次数。
//
//	这个矩阵具有以下特性：
//
//	每行中的整数从左到右是排序的。
//	每一列的整数从上到下是排序的。
//	在每一行或每一列中没有重复的整数。
//	您在真实的面试中是否遇到过这个题？  
//	样例
//	考虑下列矩阵：
//
//	[
//
//	    [1, 3, 5, 7],
//
//	    [2, 4, 7, 8],
//
//	    [3, 5, 9, 10]
//
//	]
//
//	给出target = 3，返回 2
//
//	挑战
//	要求O(m+n) 时间复杂度和O(1) 额外空间
	public static void main(String[] args) {
		int[][] nums= {
		               {1, 3, 5, 7},
		               {2, 4, 7, 8},
		               {3, 5, 9, 10} 
		               };
		System.out.println(searchMatrix(nums,3));
	}
	
	public static int searchMatrix(int[][] matrix, int target) {
		int m=matrix.length;
		if(m<=0)return 0;
		int n=matrix[0].length;
		if(n<=0)return 0;
		int count=0;
		for(int i=0;i<m;i++) {
			if(target>=matrix[i][0]&&target<=matrix[i][n-1]) {
				for(int j=0;j<n;j++) {
					if(target>=matrix[0][j]&&target<=matrix[m-1][j]) {
						if(matrix[i][j]==target) {
							count++;
							break;
						}
					}
				}
			}
		}
		return count;
	}
}
